package com.power.algorithm.structure.heap;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/5/24 1:20 下午
 */

public class MaxHeap {
    public int[] heap;
    private int CAPACITY = 10;
    private int size;
    private int INDEX = 0;

    public MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    public MaxHeap() {
        this(10);
    }


    //获取父节点的索引
    public int getParent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("没有父节点");
        }
        return (index - 1) / 2;
    }


    //获取左子节点索引
    public int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    //获取右子节点索引
    public int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    //获取左子节点值
    public int getLeftChildData(int index) {
        return heap[index * 2 + 1];
    }

    //获取右子节点值
    public int getRightChildData(int index) {
        return heap[index * 2 + 2];
    }


    //获取当前节点的值
    public int getCurrentData(int index) {
        return heap[index];
    }

    //是否存在左子节点
    public boolean isExistLeftChildIndex(int index) {
        if (index * 2 + 1 >= size) {
            return false;
        }
        return true;
    }

    //是否存在右子节点
    public boolean isExistRightChildIndex(int index) {
        if (index * 2 + 2 >= size) {
            return false;
        }
        return true;
    }

    //获取堆大小
    public int getSize() {
        return size;
    }

    //判断堆是否为空
    public boolean isEmpty() {
        if (size == 0) {
            return true;
        }
        return false;
    }

    //插入一个节点元素
    public void insert(int element) {
        if (size == 0) {
            //如果为空堆  则这个节点为空堆
            heap[INDEX++] = element;
            size++;
            return;
        }
        //如果不为空堆 则进行元素的上浮
        heap[INDEX++] = element;
        size++;
        //直到当前节点没有父节点结束
        int currentIndex = getLastElement();
        int parentIndex = -1;
        //如果存在父节点  就执行比较交换操作
        //入股不存在父节点就结束
        while (isExistParent(currentIndex)) {
            parentIndex = getParent(currentIndex);
            //如果当前元素  大于父节点就交换地柜
            if (compare(heap[currentIndex], heap[parentIndex])) {
                //交换数据
                swap(currentIndex, parentIndex);
                currentIndex = parentIndex;
                //如果当前元素比父元素小 则结束这个循环
            } else {
                return;
            }
        }
    }

    //移除一个元素
    public void remove(int element) {
        for (int i = 0; i < size; i++) {
            if (this.heap[i] == element) {
                //删除元素  并且下沉操作
                //将最后一个元素赋值过来  然后删掉最后一个值
                swap(i, size - 1);
                size--;

                /**
                 * 1. 获取左子树的节点的值   如果比左子树大则不变   如果比左子树小则交换到满足位置
                 * 2. 如果左子树比节点值大 则比较右子树  如果右子树比较大 则交换到满意  否则结束条件
                 */
                //子树存在的情况
                int currentIndex = i;
                int childIndex = -1;
                int value = element;
                while (isExistLeftChildIndex(currentIndex) || isExistRightChildIndex(currentIndex)) {

                    if (getLeftChildData(currentIndex) > getCurrentData(currentIndex)) {
                        //获取左子树的节点索引
                        childIndex = getLeftChildIndex(currentIndex);
                        //交换左子树与当前节点的值
                        swap(getLeftChildIndex(currentIndex), currentIndex);
                        //左子树的节点等于当前节点
                        currentIndex = getLeftChildIndex(currentIndex);
                    } else if (getRightChildData(i) > getCurrentData(currentIndex)) {
                        childIndex = getRightChildIndex(currentIndex);
                        //如果右子树大于当前元素 交换右子树与当前元素
                        swap(getRightChildIndex(currentIndex), currentIndex);
                        //右节点等于当前节点
                        currentIndex = getRightChildIndex(currentIndex);
                    } else {
                        break;
                    }
                }
                //子树不存在的情况
                return;
            }
        }

    }


    public boolean isExistParent(int index) {
        if (index == 0) {
            return false;
        }
        //如果父元素的索引>=0 是有父元素
        if ((index - 1) / 2 >= 0) {
            return true;
        }
        //如果索引<0 则不存在父索引
        return false;
    }


    //获取末尾元素索引
    public int getLastElement() {
        return this.size - 1;
    }

    //交换向量中的值
    public void swap(int a, int b) {
        int dataA = this.get(a);
        int dataB = this.get(b);
        this.set(a, dataB);
        this.set(b, dataA);
    }

    public void set(int index, int element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("数组越界");
        }
        this.heap[index] = element;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("数组越界");
        }
        return this.heap[index];
    }

    public boolean compare(int a, int b) {
        if (a > b) {
            return true;
        }
        return false;
    }


    public int getCAPACITY() {
        return CAPACITY;
    }

    public void display() {
        System.out.println("----------start---------------");
        System.out.print("堆中元素为:: ");
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }

        System.out.println("\nheap size::: " + getSize());
        System.out.println("heap Capacity::: " + getCAPACITY());
        System.out.println("----------end---------------");
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(1);
        maxHeap.insert(3);
        maxHeap.insert(5);
        maxHeap.insert(8);
        maxHeap.insert(6);
        maxHeap.insert(9);
        maxHeap.display();
        maxHeap.remove(6);
        maxHeap.display();
        // System.out.println((int)((2-1)/2));
    }


}


/**
 * 1.构建队列
 * 2. 增加元素()
 * 3. 删除元素()
 * 4.判断队列是否满了
 * 5.判断队列是否为空
 * 6. 查找父节点
 * 7. 查找左子树节点
 * 8. 查找右子树节点
 */
